In the concealed search system, a searcher can search data saved in a server, by specifying a keyword. In the search, the data and keyword are concealed from the server. The concealed search system is expected to be applied to the outsourcing of confidential data management and the filtering of encrypted mail in a mail server. Various techniques have been proposed for the concealed search system such as a technique to achieve different types of security requirements as well as techniques to reduce the server storage, a searcher storage, communication overhead, and computation overhead.
The concealed search can be roughly classified into those that are based on deterministic encryption and those that are based on probabilistic encryption. The concealed search based on deterministic encryption is advantageous because, since the same keyword corresponds to the same encrypted keyword, the server only needs to conduct a binary matching check based on a specified encrypted keyword, enabling high-speed concealed search employing an existing search technique. The keyword frequency information, however, directly appears as the encrypted keyword frequency information. This leads to a defect that an attack called “frequency analysis” is possible in which the server estimates a corresponding keyword by examining the encrypted keyword frequency.
On the other hand, in the concealed search based on probabilistic encryption, since different encrypted keywords are generated from the same keyword, the keyword frequency information is not saved, and the system is not exposed to the frequency analysis attack described above. Instead, collation of the encrypted keyword and a search request (trapdoor) requires particular computation that is not a binary matching check. Also, the high-speed technique employed in ordinary search cannot be employed. Therefore, there is a problem that a lot of time is spent until the search is completed. As a countermeasure for this problem, a method is available that employs probabilistic encryption and deterministic encryption so that both the security of the probabilistic encryption and the high speed performance of the deterministic encryption are achieved.
Patent Literature 1 discloses a method of searching the value of a probabilistic encryption at a high speed by preparing a table that stores the value of the probabilistic encryption and a table that stores the value of the deterministic encryption and utilizing a table that holds an encrypted relation between the two tables.